class Solution {
public:
    int getMissingNumber(vector<int>& nums) {
        if(nums.empty())
            return 0;
        int left=0,right=nums.size()-1;
        while(left<=right){
            int mid=(left+right)>>1;
            if(nums[mid]==mid)
                left=mid+1;
            else{
                if(mid==0||nums[mid-1]==mid-1)
                    return mid;
                right=mid-1;
            }
            if(left==nums.size())
                return left;
        }
        return -1;
    }
};